package cn.tansanqinger.linked;

import java.util.Arrays;

interface ITree<T>{
    void add(T data);
    int size();
    T[] toArrayFornt();//中序遍历
    T[] toArrayCentre();//中序遍历
    T[] toArrayQueen();//中序遍历
    boolean query(T data);//查询数据
    void remove(T data);//删除节点
}
class TreeImpl<T> implements ITree<T>{
    private Node root ;//保存根结点
    private int size ;//保存树中数据个数
    private T[] returnData;//保存数据
    private int len;//数组下标
    @Override
    public void add(T data) {
        if(data==null) return ;
        Comparable result = (Comparable) data;
        Node newNode = new Node(result);
        if(root==null){
            this.root = newNode;
        } else {
            this.root.addNode(this.root, newNode);
        }
        this.size ++;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public T[] toArrayFornt() {
        if(this.size==0) return null;
        this.len = 0;
        returnData = (T[]) new Object[this.size];
        this.root.toArrayNodeFront();
        return returnData;
    }

    @Override
    public T[] toArrayCentre() {
        if(this.size==0) return null;
        this.len = 0;
        returnData = (T[]) new Object[this.size];
        this.root.toArrayNodeCenter();
        return returnData;
    }

    @Override
    public T[] toArrayQueen() {
        if(this.size==0) return null;
        this.len = 0;
        returnData = (T[]) new Object[this.size];
        this.root.toArrayNodeQueen();
        return returnData;
    }

    @Override
    public boolean query(T data) {
        if(this.size == 0) return  false;
        return this.root.queryNode(data);
    }

    @Override
    public void remove(T data) {
        Node deleteNode = this.root.queryRemoveNode(data);//查询要删除的节点
        if(deleteNode!=null){
            if(deleteNode == root){//该节点是否为根结点
                if(this.size==1){
                    this.root = null;
                }
                this.root = removeNode(deleteNode);
            } else {
                removeNode(deleteNode);
            }
        }
        this.size--;
    }
    private Node removeNode(Node deleteNode){
        Node moveSubNode = null;
        if(deleteNode.left == null && deleteNode.right == null){//该节点是否是叶子节点
            if(deleteNode.parent.left == deleteNode){//该节点位于左边
                deleteNode.parent.left = null;
            } else {
                deleteNode.parent.right = null;//位于右边
            }
        }
        if((deleteNode.left != null & deleteNode.right == null)||
                (deleteNode.left == null & deleteNode.right != null)) {
            moveSubNode = null;//要移动的节点，可能是左节点，或者右节点
            if(deleteNode.left != null) {
                moveSubNode = deleteNode.left;
            }else {
                moveSubNode = deleteNode.right;
            }
            if(deleteNode.parent != null) {
                if(deleteNode.parent.left == deleteNode){//该节点位于左边
                    deleteNode.parent.left = moveSubNode;//移动子节点
                }else {
                    deleteNode.parent.right = moveSubNode;//移动子节点
                }
            }
            moveSubNode.parent = deleteNode.parent;//修改父节点
        }
        if(deleteNode.left != null && deleteNode.right != null) {
            moveSubNode = deleteNode.right;//获取移动节点
            while(moveSubNode.left!=null) {
                this.len++;
                moveSubNode = moveSubNode.left;//找到最左的节点
            }
            if(moveSubNode.right != null) {//移动节点存在有右节点
                moveSubNode.parent.left = moveSubNode.right;
                moveSubNode.right.parent = moveSubNode.parent;
            }else {
                if(deleteNode.right != moveSubNode) {
                    moveSubNode.parent.left = null;//删除移动节点对应的左节点
                }
            }
            moveSubNode.parent = deleteNode.parent;//改变移动节点的父节点
            moveSubNode.left = deleteNode.left;
            if(deleteNode.right != moveSubNode) {
                moveSubNode.right = deleteNode.right;
            }
            if(deleteNode.parent != null) {
                if(deleteNode.parent.left == deleteNode){//该节点位于左边
                    deleteNode.parent.left = moveSubNode;//移动子节点
                }else {
                    deleteNode.parent.right = moveSubNode;//移动子节点
                }
            }
        }
        return moveSubNode;
    }
    class Node{
        private Node left;//左节点
        private Node right;//右节点
        private Node parent;//父节点
        private Comparable<T> data;
        private Node(Comparable<T> data){
            this.data = data;
        }
        private void addNode(Node parentNode , Node newNode){
            if(this.data.compareTo((T) newNode.data)<=0){//添加的数据大于节点数据
                if(this.right==null){//右子节点是否为空
                    this.right = newNode;//将数据放到右子节点
                    newNode.parent = parentNode;//为子节点上添加父结点
                } else {
                    this.right.addNode(this.right,newNode);//否则继续向下判断
                }
            } else {//数据小于父结点，放左边
                if(this.left==null){//和上面类是的操作
                    this.left = newNode;
                    newNode.parent = parentNode;
                } else {
                    this.left.addNode(this.left,newNode);
                }
            }
        }
        private void toArrayNodeFront(){
            TreeImpl.this.returnData[TreeImpl.this.len++] = (T) this.data;
            if(this.left!=null){
                this.left.toArrayNodeFront();
            }
            if(this.right!=null){
                this.right.toArrayNodeFront();
            }
        }
        private void toArrayNodeCenter(){
            if(this.left!=null){
                this.left.toArrayNodeCenter();
            }
            TreeImpl.this.returnData[TreeImpl.this.len++] = (T) this.data;
            if(this.right!=null){
                this.right.toArrayNodeCenter();
            }
        }
        private void toArrayNodeQueen(){
            if(this.left!=null){
                this.left.toArrayNodeQueen();
            }
            if(this.right!=null){
                this.right.toArrayNodeQueen();
            }
            TreeImpl.this.returnData[TreeImpl.this.len++] = (T) this.data;
        }
        private boolean queryNode(T data){
            if(this.data.equals(data)){//这里使用compareTo进行判断也是可以的，在自定义类中都需要覆写这两个方法。
                return true;
            } else {
                if(this.data.compareTo(data)<0){//判断到哪边查找数据
                    if(this.right!=null){//右子节点还有数据，继续向下
                        return this.right.queryNode(data);
                    } else {
                        return false;//没有数据返回false
                    }
                } else {
                    if(this.left != null){//继续向左子节点查询
                        return this.left.queryNode(data);
                    } else {
                        return false;
                    }
                }
            }
        }
        private Node queryRemoveNode(T data){//查询要删除的数据是否存在
            if(this.data.equals(data)){
                return this;
            } else {
                if(this.data.compareTo(data)<0){
                    if(this.right != null){
                        return this.right.queryRemoveNode(data);
                    } else {
                        return null;
                    }
                } else {
                    if(this.left != null){
                       return this.left.queryRemoveNode(data);
                    } else {
                        return null;
                    }
                }
            }
        }
    }
}
public class TreeDemo {
    public static void main(String[] args) {
        ITree tree = new TreeImpl();
        tree.add(55);
        tree.add(12);
        tree.add(34);
        tree.add(88);
        tree.add(66);
        tree.add(99);
        tree.add(8);
        System.out.println(Arrays.toString(tree.toArrayFornt()));
        System.out.println(Arrays.toString(tree.toArrayCentre()));
        System.out.println(Arrays.toString(tree.toArrayQueen()));
        tree.remove(8);//叶子节点
        System.out.println(Arrays.toString(tree.toArrayCentre()));
        tree.remove(12);//只有一个子节点
        System.out.println(Arrays.toString(tree.toArrayCentre()));
        tree.remove(55);//删除根节点
        System.out.println(Arrays.toString(tree.toArrayCentre()));
    }
}
